/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-04-08
 * Time: 11:02
 */
//918.环形子数组的最大和
class Solution2 {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        f[0] = 0;g[0] = 0;
        int ret = Integer.MIN_VALUE;
        int tmp = Integer.MAX_VALUE;
        int sum = 0;
        for(int i = 1; i <=n; i++) {
            f[i] = Math.max(f[i-1]+nums[i-1],nums[i-1]);
            ret = Math.max(ret,f[i]);
            g[i] = Math.min(g[i-1]+nums[i-1],nums[i-1]);
            tmp = Math.min(tmp,g[i]);
            sum += nums[i-1];
        }
        return sum == tmp ? ret : Math.max(ret,sum-tmp);
    }
}